// 给定一个m * n的有序二维矩阵matrix，矩阵中每行元素从左到右升序排列，每行的第一个整数大于前一行的最后一个整数，
// 再给定一个目标值target，要求判断矩阵中是否存在目标值target

// 思路：利用题目中每行从左到右升序，每行同列升序，从矩阵的左下角开始判断
// 时间复杂度：O(m+n)
// 空间复杂度：O(1)
function searchMatrix(matrix, target) {
    if (!matrix.length || !matrix[0].length) {
        return false
    }
    let m = matrix.length - 1
    let n = matrix[0].length - 1
    let row = m
    let col = 0
    while (row >= 0 && col <= n) {
        if (matrix[row][col] < target) {
            col++
        } else if (matrix[row][col] > target) {
            row--
        } else {
            return true
        }
    }
    return false
}

let matrix2 = [
    [1,4,7,11,15],
    [2,5,8,12,19],
    [3,6,9,16,22],
    [10,13,14,17,24],
    [18,21,23,26,30]
], target = 16

console.log(searchMatrix(matrix2, target))